// 12.1　有旋Treap
function rotateImpl(tree, node, dir, setParent) {
    var other = dir == 'left' ? 'right' : 'left';
    if (!node[other]) {
      return;
    }
    var top = node[other]; // 会上浮的孩子结点
    node[other] = top[dir]; // 过继孩子结点
    if (setParent) {
      if (!node.parent) {
        tree.root = top;
      } else if (node == node.parent.left) {
        node.parent.left = top;
      } else {
        node.parent.right = top;
      }
      Object(top[dir]).parent = node; // 父属性修正1
      top.parent = node.parent; // 父属性修正2
      node.parent = top; // 父属性修正3
    }
    top[dir] = node; // 旋转
    node.maintain(); // 先处理下面的再处理上面的
    top.maintain();
    return top;
} 
// class Node {
//     constructor(data) {
//       this.data = data;
//       this.right = null;
//       this.left = null;
//       this.fix = ~~(Math.random() + "").slice(2, 7);
//       this.size = 1;
//       this.count = 1;
//     }
//     maintain() {
//       this.size = this.count;
//       if (this.left) {
//         this.size += this.left.size;
//       }
//       if (this.right) {
//         this.size += this.right.size;
//       }
//     }
// }
// class Treap {
//     constructor() {
//       this.root = null;
//     }
// // 12.1.2　插入
//     //test
//   insert(value) {
//     this.root = this._insert(this.root, value);
//     getOrder(this);
//   }
//     // insert(value) {
//     //     this.root = this._insert(this.root, value);
//     // }
//     _insert(node, value) {
//         if (!node) {
//             return new Node(value);
//         }
//         if (node.data == value) {
//             node.count++;
//             node.maintain();
//             return node;
//         } else if (node.data > value) {
//             node.left = this._insert(node.left, value);
//             if (node.left.fix < node.fix) {
//             node = this.rotateRight(node);
//             }
//         } else {
//             node.right = this._insert(node.right, value);
//             if (node.right.fix < node.fix) {
//             node = this.rotateLeft(node);
//             }
//         }
//         node.maintain();
//         return node;
//     }
//     rotateLeft(node) {
//         return rotateImpl(this, node, 'left', false);
//     }
    
//     rotateRight(node) {
//         return rotateImpl(this, node, 'right', false);
//     }
// // 12.1.3　查找
//     find(value) {
//         var node = this.root;
//         while (node) {
//           var diff = value - node.data;
//           if (value === 0) {
//             return node;;;
//           } else if (value > 0) {
//             node = node.right;
//           } else {
//             node = node.left;
//           }
//         }
//         return null;
//     }
// // 12.1.4　删除
//     remove(value) {
//         var parents = [],
//             node = this.root;
//         while (node) {
//           var diff = value - node.data;
//           if (diff === 0) {
//             break;
//           }
//           parents.push(node);
//           if (diff > 0) {
//             node = node.right;
//           } else {
//             node = node.left;
//           }
//         }
//         if (node) { // 找到要删除的结点
//           console.log("找到要删除的结点", node);
//           if (node.count > 1) {
//             node.count--;
//           } else {
//             var parent = parents[parents.length - 1],
//                 newParent;
//             while (node.left && node.right) {
//               var dir = Object(parent).left == node ? 'left' : 'right';
//               if (node.left.fix < node.right.fix) {
//                 // left上位
//                 newParent = this.rotateRight(node);
//                 console.log('右旋', newParent.data);
//               } else {
//                 newParent = this.rotateLeft(node);
//                 console.log('左旋', newParent.data);
//                 // right上位
//               }
//               if (!parent) {
//                 this.root = newParent;
//               } else {
//                 parent[dir] = newParent;
//               }
//               parent = newParent;
//               parents.push(parent);
//             }
      
//             var dir = Object(parent).left == node ? 'left' : 'right';
//             parent[dir] = node.left || node.right || null;
//           }
//           console.log("找到要维护的父结点", parents.map(function(el) {
//             return el.data;
//           }));
//           while (parents.length) {
//             var a = parents.pop();
//             a.maintain();
//           }
//           return true;
//         }
//         return false;
//     }
// // 12.1.5　三种遍历
//     inOrder(cb) { // 中序遍历
//         function recursion(node) {
//           if (node) {
//             recursion(node.left);
//             cb(node);
//             recursion(node.right);
//           }
//         }
//         recursion(this.root);
//     }
//     preOrder(cb) { // 前序遍历
//         function recursion(node) {
//           if (node) {
//             cb(node);
//             recursion(node.left);
//             recursion(node.right);
//           }
//         }
//         recursion(this.root);
//     }
//     postOrder(cb) { // 后序遍历
//         function recursion(node) {
//           if (node) {
//             recursion(node.left);
//             recursion(node.right);
//             cb(node);
//           }
//         }
//         recursion(this.root);
//     }
// // 12.1.6　获取value的排名
//     getRank(value) {
//         return this.getRankInner(this.root, value);
//     }
//     getSize(node) {
//         return node ? node.size : 0;
//     }
//     getRankInner(node, value) {
//         if (!node) {
//         return 0;
//         } else if (node.data == value) {
//         return this.getSize(node.left) + 1;
//         } else if (node.data > value) {
//         return this.getRankInner(node.left, value);
//         } else {
//         return this.getRankInner(node.right, value) + this.getSize(node.left) + node.count;
//         }
//     }
// // 12.1.7　根据排名找对应的数
//   getKth(k) {
//     var node = this.root;
//     while (node) {
//       if (k <= this.getSize(node.left)) {
//         node = node.left;
//       } else if (k > this.getSize(node.left) + node.count) {
//         k -= (this.getSize(node.left) + node.count);
//         node = node.right;
//       } else {
//         return node.data;
//       }
//     }
//     return null;
//   }
// }

// var array = [7, 11, 13, 8, 44, 78, 15, 9, 77, 1, 2];
// var t = new Treap();
// array.forEach(function(el) {
//   t.insert(el);
// });

// function getOrder(t) {
//   var array = [];
//   t.inOrder(function(node) {
//     array.push(node.data);
//   });
//   console.log(array + "");
// }
// var a = t.getRank(44);
// console.log('t.getRank(44)', a);
// var b = t.getKth(a);
// console.log(`t.getKth(${a})`, b);
// console.log("移除11,3后");
// t.remove(11);
// t.remove(3);
// t.insert(23);


// 12.2　无旋Treap
// class Node {
//     constructor(value) {
//       this.left = null;
//       this.right = null;
//       this.size = 1;
//       this.data = value;
//       this.fix = ~~(Math.random() + "").slice(2, 5);
//     }
//     maintain() {
//       var leftSize = this.left ? this.left.size : 0;
//       var rightSize = this.right ? this.right.size : 0;
//       this.size = leftSize + rightSize + 1;
//     }
// }
  
// function Pair(a, b) { // 用于拆分与合并
//     this.first = a;
//     this.second = b;
// }
// class Treap {
//     constructor(mode) {
//       this.root = null;
//     }
// // 12.2.1　合并
//     merge(a, b) { // 此时a树所有结点的值都应小于b中所有结点的值
//         if (!a || !b) { // 如果有一个为空，那么返回不为空的
//           return a || b;
//         }
//         if (a.fix < b.fix) { // 要满足堆的性质
//           a.right = this.merge(a.right, b);
//           a.maintain(); // 维护它的结点大小
//           return a;
//         } else {
//           b.left = this.merge(a, b.left);
//           b.maintain(); // 维护它的结点大小
//           return b;
//         }
//     }
// // 12.2.2　拆分
//     split(node, value) {
//         if (!node) {
//           return new Pair(null, null);
//         }
//         var p; // pair
//         if (node.data <= value) {
//           p = this.split(node.right, value);
//           node.right = p.first;
//           p.first = node;
//         } else {
//           p = this.split(node.left, value);
//           node.left = p.second;
//           p.second = node;
//         }
//         node.maintain();
//         return p;
//     }
// // 12.2.3　添加
//     insert(value) {
//         var p = this.split(this.root, value);
//         var node = new Node(value);
//         this.root = this.merge(this.merge(p.first, node), p.second);
//         getOrder(this);
//     }
// // 12.2.4　移除
//     remove(value) {
//         // 留意split里面蓝红树是用 <=拆分的
//         // 大于value的结点包含在p1.first中
//         var p1 = this.split(this.root, value);
//         var p2 = this.split(p1.first, value - 1);
//         // value孤零零地放在p2.second中
//         this.root = this.merge(p2.first, p1.second);
//     }
//     // 12.2.5　查找
//     find(value) {
//         // <=> value包含在p1.first中
//         var p1 = this.split(this.root, value);
//         var p2 = this.split(p1.first, value - 1);
//         // value孤零零地放在p2.second中
//         this.root = this.merge(p1.first, p2.second);
//         return p2.second;
//     }
//     // 12.2.6　获取value的排名
//     getRank(value) { // 从1数起
//         var p = this.split(this.root, value - 1);
//         var ans = this.getSize(p.first) + 1;
//         this.root = this.merge(p.first, p.second);
//         return ans;
//     }
//     // 12.2.7　根据排名找对应的数
//     getValueBySize(node, k) {
//         while (node) {
//           var lsize = this.getSize(node.left);
//           if (lsize + 1 === k) {
//             return node.data;
//           } else if (lsize + 1 > k) {
//             node = node.left;
//           } else {
//             k -= (lsize + 1);
//             node = node.right;
//           }
//         }
//         return 0;
//       }
//     getKth(rank) {
//         return this.getValueBySize(this.root, rank);
//     }
//     // 12.2.8　求前驱结点和后继结点
//     getPrev(value) { // 获取前驱结点
//         var p = this.split(this.root, value - 1);
//         var ans = this.getValueBySize(p.first, this.getSize(p.first));
//         this.root = this.merge(p.first, p.second);
//         return ans;
//     }
//     getSucc(value) { // 获取后继结点
//         var p = this.split(this.root, value);
//         var ans = this.getValueBySize(p.second, 1);
//         this.root = this.merge(p.first, p.second);
//         return ans;
//     }
//     // 12.2.9　求最大值和最小值
//     getMin() {
//         return this.getValueBySize(this.root, 1);
//       }
//     getMax() {
//         return this.getValueBySize(this.root, this.getSize(this.root));
//     }
//     //
//     inOrder(cb) { // 中序遍历
//         function recursion(node) {
//           if (node) {
//             recursion(node.left);
//             cb(node);
//             recursion(node.right);
//           }
//         }
//         recursion(this.root);
//     }
//     getSize(node) {
//         return node ? node.size : 0;
//     }
// }  
// var array = [7, 11, 13, 8, 44, 78, 15, 9, 77, 1, 2];
// var t = new Treap();
// array.forEach(function(el) {
//   t.insert(el);
// });

// function getOrder(t) {
//   var array = [];
//   t.inOrder(function(node) {
//     array.push(node.data);
//   });
//   console.log(array + "");
// }
// var a = t.getRank(44);
// console.log('t.getRank(44)', a);
// var b = t.getKth(a);
// console.log(`t.getKth(${a})`, b);
// console.log(`t.getPrev(44)`, t.getPrev(44));
// console.log(`t.getSucc(44)`, t.getSucc(44));
// console.log('t.getMin()', t.getMin());



// 12.3　伸展树

// class Node {
//     constructor(data) {
//       this.data = data;
//       this.parent = null;
//       this.left = null;
//       this.right = null;
//       this.size = 1; // 用于排名
//     }
//     maintain() {
//       var leftSize = this.left ? this.left.size : 0;
//       var rightSize = this.right ? this.right.size : 0;
//       this.size = leftSize + rightSize + 1;
//     }
//   }
  
// function rotateImpl(tree, node, dir, setParent) {
//     var other = dir == 'left' ? 'right' : 'left';
//     if (!node[other]) {
//       return;
//     }
//     var top = node[other]; // 会上浮的孩子结点
//     node[other] = top[dir]; // 过继孩子结点
//     if (setParent) {
//       if (!node.parent) {
//         tree.root = top;
//       } else if (node == node.parent.left) {
//         node.parent.left = top;
//       } else {
//         node.parent.right = top;
//       }
//       Object(top[dir]).parent = node; // 父属性修正1
//       top.parent = node.parent; // 父属性修正2
//       node.parent = top; // 父属性修正3
//     }
//     top[dir] = node; // 旋转
//     node.maintain(); // 先处理下面的再处理上面的
//     top.maintain();
//     return top;
// } 
//   class SplayTree {
//     constructor() {
//       this.root = null;
//     }
//     rotate(x) { // rotate具有决定左旋或右旋的功能
//         var p = x.parent;
//         if (x === p.left) {
//           return this.rightRotate(p);
//         } else {
//           return this.leftRotate(p);
//         }
//     }
//     leftRotate(node) {
//       return rotateImpl(this, node, 'left', true);
//     }
//     rightRotate(node) {
//       return rotateImpl(this, node, 'right', true);
//     }
//     // splay(node, goal) {
//     //   if (node == goal) return;
//     //   while (node.parent != goal) {
//     //     var parent = node.parent;
//     //     if (parent == goal) { // 如果父结点是根结点
//     //       if (parent.left == node) {
//     //         this.rightRotate(parent);
//     //       } else {
//     //         this.leftRotate(parent);
//     //       }
//     //       break;
//     //     } else { // 如果祖父结点是根结点
//     //       var grandpa = parent.parent;
//     //       var case1 = grandpa.left === parent ? "zig-" : "zag-";
//     //       var case2 = parent.left === node ? "zig" : "zag";
//     //       switch (case1 + case2) {
//     //         case "zig-zig": // 一字形，先父后子，因为我们的旋转操作都针对根结点
//     //           // 操作node，即操作parent
//     //           this.rightRotate(grandpa);
//     //           this.rightRotate(parent);
//     //           continue;
//     //         case "zag-zag": // 一字形，先父后子
//     //           this.leftRotate(grandpa);
//     //           this.leftRotate(parent);
//     //           continue;
//     //         case "zig-zag": // 之字形
//     //           this.leftRotate(parent);
//     //           this.rightRotate(grandpa);
//     //           continue;
//     //         case "zag-zig": // 之字形
//     //           this.rightRotate(parent);
//     //           this.leftRotate(grandpa);
//     //           continue;
//     //       }
//     //     }
//     //   }
//     // }
//     splay(node, goal) {
//         if (node == goal) return;
//         while (node.parent != goal) {
//           var p = node.parent;
//           if (p.parent == goal) { // 如果祖先不存在，单旋
//             this.rotate(node);
//             break;
//           }
//           // 如果有两个可以旋转的父级结点
//           // 那么判断它们是否位于同一条线上，如果是，就使用一字形旋转
//           // 否则就使用之字形旋转
//           var grandpa = p.parent;
//           this.rotate(
//             (node === p.left) === (p === grandpa.left) ? p : node
//           );
//           this.rotate(node);
//         }
//         console.log(node, 'p.parent == goal')
//     }
//     // 12.3.2　查找
//     find(value) {
//         var node = this.root;
//         while (node) {
//           var diff = value - node.data;
//           if (diff == 0) {
//             break;
//           } else if (diff < 0) {
//             node = node.left;
//           } else {
//             node = node.right;
//           }
//         }
//         if (node) {
//           this.splay(node);
//           return node;
//         }
//         return null;
//     }
//     insert(value) {
//         if (!this.root) {
//           this.root = new Node(value);
//           return true;
//         }
//         var node = this.root,
//             parent = null,
//             diff;
//         while (node) {
//           parent = node; // 保存要插入的父结点
//           diff = value - node.data;
//           if (diff == 0) {
//             return false;
//           } else if (diff < 0) {
//             node = node.left;
//           } else {
//             node = node.right;
//           }
//         }
//         var node = new Node(value);
//         node.parent = parent;
//         if (diff < 0) {
//           parent.left = node;
//         } else {
//           parent.right = node;
//         }
//         this.splay(node);
//         return true;
//     }
//     toString(printNode) {
//         if (!printNode) {
//           printNode = function(node) {
//             return node.data;
//           };
//         }
//         var out = [];
//         printRow(this.root, '', true, function(v) {
//           return out.push(v);
//         }, printNode);
//         return out.join('');
//     }
//     // 12.3.4　删除
//     remove(data) {
//         let node = this.find(data);
//         if (!node) {
//           return false;
//         } else {
//           if (node.count > 1) {
//             node.count--;
//             return true;
//           }
//           if (node.left && node.right) {
//             var succ = this.maxNode(node.left); // 求后继结点
//             node.data = succ.data;
//             node = succ; // 转为一个孩子结点的情况
//           }
//           // 一个或零个孩子结点的情况
//           var child = node.left || node.right || null;
//           var parent = node.parent;
//           if (parent.left == node) {
//             parent.left = child;
//           } else {
//             parent.right = child;
//           }
//           if (child) {
//             child.parent = parent; // parent的size发生变化
//             this.splay(child);
//           }
//           return true;
//         }
//     }
//     // 12.3.5　区间删除
//     removeRange(start, end) {
//         if (start >= end) {
//           throw 'start必须小于end';
//         }
//         var a = this.getKth(start - 1);
//         var b = this.getKth(end + 1);
//         a = this.find(a);
//         b = this.find(b);
//         if (!a && !b) {
//           return;
//         }
//         if (!a) {
//           this.splay(b);
//           b.left = null;
//           b.maintain();
//           return;
//         }
//         if (!b) {
//           this.splay(a);
//           a.right = null;
//           a.maintain();
//           return;
//         }
//         this.splay(a);
//         this.splay(b, a);
//         b.left = null;
//         b.maintain();
//     }
//     // 12.3.6　获取value的排名
//     getRank(value) {
//         var node = this.find(value);
//         if (node) {
//           return this.getSize(node.left) + 1;
//         } else {
//           return 0;
//         }
//     }
//     // 12.3.7　求最大值和最小值
//     maxNode(node) {
//         var cur = node || this.root;
//         while (cur.right) {
//           cur = cur.right;
//         }
//         return cur;
//     }
//     minNode(node) {
//         var cur = node || this.root;
//         while (cur.left) {
//           cur = cur.left;
//         }
//         return cur;
//     }
//     getMax() {
//         var node = this.maxNode();
//         return node ? node.data : null;
//     }
//     getMin() {
//         var node = this.minNode();
//         return node ? node.data : null;
//     }
//     // 12.3.8　求前驱结点和后继结点
//     getPrev(value) { // 找value的前驱结点
//         var node = this.find(value);
//         if (node) {
//           this.splay(node);
//           return this.maxNode(node.right);
//         }
//     }
//     getSuss(value) { // 找value的后继结点
//         var node = this.find(value);
//         if (node) {
//           this.splay(node);
//           return this.minNode(node.left);
//         }
//     } 
//     // 12.3.9　合并
//     merge(first, second) {
//         if (!first) {
//           return second;
//         }
//         if (!second) {
//           return first;
//         }
//         var max = this.maxNode(first);
//         this.splay(max, first);
//         max.right = second;
//         second.parent = max;
//         return max;
//     }
//     // 12.3.10　拆分   
//     approximate(node, value) { // 小于或等于value
//         if (!node) {
//           return null;
//         }
//         while (node.data != data) {
//           if (data < node.data) {
//             if (!node.left) break;
//             node = node.left;
//           } else {
//             if (!node.right) break;
//             node = node.right;
//           }
//         }
//         return node.data;
//     }
//     split(value) {
//         var trees = [];
//         var data = this.approximate(this.root, value);
//         if (data == null) {
//           return trees;
//         }
//         var tree1 = new SplayTree();
//         var tree2 = new SplayTree();
//         var node = this.find(data);
//         // 将前驱结点旋转为根结点
//         this.splay(node);
//         var root = this.root;
//         tree1.root = root;
//         tree2.root = root.right;
//         if (root.right != null) {
//           root.right.parent = null;
//         }
//         root.right = null;
//         trees.push(tree1, tree2);
//         return trees;
//     }
// }
function printRow(root, prefix, isTail, out, printNode) {
    if (root) {
      out(("" + prefix + (isTail ? '└── ' : '├── ') + (printNode(root)) + "\n"));
      var indent = prefix + (isTail ? '    ' : '│   ');
      if (root.left) {
        printRow(root.left, indent, false, out, printNode);
      }
      if (root.right) {
        printRow(root.right, indent, true, out, printNode);
      }
    }
}
// var t = new SplayTree();
// [10, 50, 40, 30, 20, 60].forEach(function(el, i) {
//   t.insert(el, i);
// });
// console.log(t.toString(), 'node');



// 12.4.1　插入
// class Node {
//     constructor(data) {
//       this.data = data;
//       this.left = null;
//       this.right = null;
//       this.parent = null;
//       this.size = 1;
//       this.count = 1;
//     }
//     maintain() {
//       this.size = this.count;
//       if (this.left) {
//         this.size += this.left.size;
//       }
//       if (this.right) {
//         this.size += this.right.size;
//       }
//     }
//   }
// class BST {
//     constructor() {
//       this.root = null;
//     }
// // 12.4.2　删除
//     remove(data) {
//         if (!this.root) {
//           return false;
//         }
//         var node = this.find(data);
//         if (node) {
//           // 两个孩子结点的情况
//           if (node.left && node.right) {
//             var succ = this.maxNode(node.left); // 求后继结点
//             node.data = succ.data;
//             node = succ; // 转为一个孩子结点的情况
//           }
//           // 一个或零个孩子结点的情况
//           var child = node.left || node.right || null;
//           var parent = node.parent;
//           if (parent.left == node) {
//             parent.left = child;
//           } else {
//             parent.right = child;
//           }
//           if (child) {
//             child.parent = parent; // parent的size发生变化
//           }
//           while (parent) {
//             parent.size--;
//             this.maintain(parent, data >= parent.data);
//             parent = parent.parent;
//           }
//         }
//     }
//     getSize(node) {
//         return node ? node.size : 0;
//     }
//     // 12.4.3　平衡
//     // maintain(node) {
//     //     var left = node.left;
//     //     var right = node.right;
//     //     var leftSize = this.getSize(left);
//     //     var rightSize = this.getSize(right);
//     //     var llSize = this.getSize(left && left.left);
//     //     var lrSize = this.getSize(left && left.right);
//     //     var rrSize = this.getSize(right && right.right);
//     //     var rlSize = this.getSize(right && right.left);
//     //     if (llSize > rightSize) {
//     //       // 左边高
//     //       this.rightLotate(node);
//     //       this.maintain(node);
//     //       right && this.maintain(right);
//     //     } else if (lrSize > rightSize) {
//     //       // 左边高
//     //       this.leftRotate(left);
//     //       this.rightRotate(node);
//     //       this.maintain(node);
//     //       right && this.maintain(right);
//     //       this.maintain(left);
//     //     } else if (rrSize > leftSize) {
//     //       // 右边高
//     //       this.leftLotate(node);
//     //       this.maintain(node);
//     //       left && this.maintain(left);
//     //     } else if (rlSize > leftSize) {
//     //       // 右边高
//     //       this.leftRotate(left);
//     //       this.leftRotate(node);
//     //       this.maintain(node);
//     //       left && this.maintain(left);
//     //       this.maintain(right);
//     //     }
//     // }
//     maintain(node, rightDeeper) {
//         if (!node) {
//           return;
//         }
//         var left = node.left;
//         var right = node.right;
//         if (!rightDeeper) {
//           if (!left) {
//             return;
//           }
//           var rightSize = this.getSize(right);
//           var llSize = this.getSize(left.left);
//           var lrSize = this.getSize(left.right);
//           if (llSize > rightSize) {
//             this.rightRotate(node);
//           } else if (lrSize > rightSize) {
//             this.leftRotate(left);
//             this.rightRotate(node);
//           } else {
//             return;
//           }
      
//         } else {
//           if (!right) {
//             return;
//           }
//           var leftSize = this.getSize(left);
//           var rrSize = this.getSize(right.right);
//           var rlSize = this.getSize(right.left);
//           if (rrSize > leftSize) {
//             this.leftRotate(node);
//           } else if (rlSize > leftSize) {
//             this.rightRotate(right);
//             this.leftRotate(node);
//           } else {
//             return;
//           }
//         }
//         this.maintain(left, false);
//         this.maintain(right, true);
//         this.maintain(node, false);
//         this.maintain(node, true);
//     }
//     leftRotate(node) {
//       return rotateImpl(this, node, 'left', true);
//     }
//     rightRotate(node) {
//       return rotateImpl(this, node, 'right', true);
//     }
//     // getKth、getRank、getMax、getMin等其他操作
//     insert(data) {
//       if (!this.root) {
//         this.root = new Node(data);
//         return true;
//       }
//       var node = this.root,
//           parent;
//       while (node) {
//         var diff = data - node.data;
//         parent = node;
//         if (diff == 0) {
//           return false;
//         } else if (diff < 0) {
//           node = node.left;
//         } else {
//           node = node.right;
//         }
//       }
//       var node = new Node(data);
//       node.parent = parent;
  
//       if (diff < 0) {
//         parent.left = node;
//       } else {
//         parent.right = node;
//       }
//       while (parent) {
//         parent.size++;
//         this.maintain(parent, data >= parent.data);
//         parent = parent.parent;
//       }
//       return true;
//     }
//     find(value) {
//         var node = this.root;
//         while (node) {
//           var diff = value - node.data;
//           if (diff == 0) {
//             break;
//           } else if (diff < 0) {
//             node = node.left;
//           } else {
//             node = node.right;
//           }
//         }
//         if (node) {
//           this.splay(node);
//           return node;
//         }
//         return null;
//     }
//     toString(printNode) {
//         if (!printNode) {
//           printNode = function(node) {
//             return node.data;
//           };
//         }
//         var out = [];
//         printRow(this.root, '', true, function(v) {
//           return out.push(v);
//         }, printNode);
//         return out.join('');
//     }
// }

// var t = new BST();
// [7, 11, 13, 8, 44, 78, 15, 9, 77, 89, 1, 2, 52, 51, 56].forEach(function(el, i) {
//   t.insert(el);
//   console.log(t + "");
// });
// console.log("delete...");
// t.remove(60);
// console.log(t.toString());


